#include<iostream>
#include<assert.h>
#include<vector>
#include<functional>
using std::cout;using std::endl;

namespace MyPQ{
  template<class T>
    class less{
      public:
      bool operator()(const T& x,const T& y)
      {
        return x < y;
      }
    };
  template<class T>
    class greater{
      public:
      bool operator()(const T& x,const T& y)
      {
        return x > y;
      }
    };
  template<class T,class container = std::vector<T>,class Compare = less<T>>
  //template<class T,class container = std::vector<T>,class Compare = greater<T>>
    class priority_queue{
      public:
        priority_queue(){}
        void push(const T& date)
        {
          //up_algorithm
          _con.push_back(date);
          int child = size()-1;
          int root = (child-1)/2;
         while(root >= 0 /*&& child > 0*/)
         {
            if(_comfunc(_con[child],_con[root]))
            {
              swap(_con[child],_con[root]);
              child = root;
              root = (child-1)/2;
            }
            else{
              break;
            }
         }
        }
        void pop()
        {
          assert(size() > 0);
          //down_algorithm
          int root = 0;
          int max = size()-1;
          if(max == root)
          {
            _con.pop_back();
            return;
          }
          swap(_con[root],_con[max--]);
          _con.pop_back();
          int child = root*2+1;
          while(child <= max)
          {
            if(child+1 <= max && _comfunc(_con[child+1],_con[child]))
            {
              child += 1;
            }
            if(_comfunc(_con[child],_con[root]))
            {
              swap(_con[child],_con[root]);
              root = child;
              child = root*2+1;
            }
            else{
              break;
            }
          }
        }
        bool empty()
        {
          return _con.empty();
        }
        size_t size()
        {
          return _con.size();
        }
        void swap(T& x,T& y)
        {
          T tmp = x;
          x = y;
          y = tmp;
        }
        T& top()
        {
          return _con[0];
        }
      private:
        container _con;
        Compare _comfunc;
    };
}
